type symbol = string
type number = int

type exprC =
    NumC of number
  | IdC of symbol
  | AppC of exprC * exprC
  | PlusC of exprC * exprC
  | MultC of exprC * exprC
  | LamC of symbol * exprC

type env = binding list
and
     binding = 
       Binding of symbol * value
and
     value =
       NumV of number
  | ClosV of symbol * exprC * env

let mt_env:env = [];;

let ext_env((b:binding),(e:env)):env = 
  b::e

exception LookupFailed;;
let rec lookup ((n:symbol),(e:env)):value =
	match e with
    [] -> raise LookupFailed
  | ar::dr -> 
	match ar with
   	Binding(name,v) ->
     if name=n then v
     else lookup(n,dr)

exception NumPlusFailed;;
let numPlus((l:value),(r:value)):value =
	match (l,r) with
	(NumV(ln),NumV(rn)) ->
		NumV(ln+rn)
	| _ -> raise NumPlusFailed


exception NumMultFailed;;
let numMult((l:value),(r:value)):value =
	match (l,r) with
	(NumV(ln),NumV(rn)) ->
		NumV(ln*rn)
	| _ -> raise NumMultFailed

exception InterpFailed;;
let rec interp ((expr:exprC),(en:env)):value =
  match expr with
    NumC(n) -> NumV(n)
  | IdC(name) -> lookup(name,en)
  | PlusC(le,re) -> numPlus(interp(le,en),
                            interp(re,en))
  | MultC(le,re) -> numMult(interp(le,en),
                            interp(re,en))
  | LamC(arg,body) -> ClosV(arg,body,en)
  | AppC(f,arg) ->
     let fvalue = interp(f,en) in
        match fvalue with
        | ClosV(fa,fb,fe) ->
          interp(fb,ext_env(Binding(fa,interp(arg,en)),fe))
        | _ -> raise InterpFailed

(*

interp(AppC(LamC("x",IdC("x")),NumC(3)),
        mt_env)

interp(AppC(LamC("x",MultC(IdC("x"),IdC("x"))),NumC(3)),
        mt_env)

lookup("a"
, ext_env(Binding("b",NumV(4)),
    ext_env (Binding("a",NumV(3)),mt_env)))
*)